package com.currentbp.Interesting.likou.cannot;

import com.currentbp.util.all.StringUtil;
import org.junit.Test;

/**
 * @author baopan
 * @createTime 2024/4/9 21:55
 */
public class T0678checkValidString {
    /*
给你一个只包含三种字符的字符串，支持的字符类型分别是 '('、')' 和 '*'。请你检验这个字符串是否为有效字符串，如果是有效字符串返回 true 。

有效字符串符合如下规则：

任何左括号 '(' 必须有相应的右括号 ')'。
任何右括号 ')' 必须有相应的左括号 '(' 。
左括号 '(' 必须在对应的右括号之前 ')'。
'*' 可以被视为单个右括号 ')' ，或单个左括号 '(' ，或一个空字符串。
一个空字符串也被视为有效字符串。
示例 1：
输入：s = "()"
输出：true
示例 2：
输入：s = "(*)"
输出：true
示例 3：
输入：s = "(*))"
输出：true
     */
    /*
    解题思路：
    1、构建一个二维数组，f[i][j]表示从第i到第j是符合有效字符串
    2、能组成有效的字符串有三种情况
    2。1、*所在的位置都是ture，即f[i][i]=true
    2.2、找出所有2个字符能组成有效的字符串
    2.3、找出所有3个字符能组成有效的字符串
    3、复杂模式
    3.1、f[i][k-1]是有效字符串，f[k][j]是有效字符串，则f[i][j]是有效字符串  todo 此处没有实现
    3.2、f[i][j]是有效字符串，(f[i][j])也是有效字符串
    3.3、
    5、最后需要求出f[0][n]的结果
     */
    @Test
    public void t1() {
//        System.out.println(checkValidString("()"));
//        System.out.println(checkValidString("(*)"));
//        System.out.println(checkValidString("(*))"));
//        System.out.println(checkValidString("()()()"));
        System.out.println(checkValidString("(((*))())()"));
    }


    public boolean checkValidString(String s) {
        boolean[][] dp = new boolean[s.length()][s.length()];
        check4Base(s, dp);

        for (int i = 0; i < s.length(); i++) {
            for (int j = 0; j < s.length(); j++) {
                check4MiddleAndSub(s, dp, i, j);

            }
            StringUtil.printObject(dp);
        }


        return dp[0][s.length() - 1];
    }

    private void check4MiddleAndSub(String s, boolean[][] dp, int start, int end) {
        if (start >= end) {
            return;
        }
        if (dp[start][end]) {
            boolean isSub = check4TwoChar(s, start - 1, end + 1);
            if (isSub) {
                dp[start - 1][end + 1] = true;
                dp[end + 1][start - 1] = true;
            }
        }
        for (int k = start + 1; k + 1 < end; k++) {
            if (dp[start][k] && dp[k + 1][end]) {
                dp[start][end] = true;
                dp[end][start] = true;
                break;
            }
        }
    }

    private void check4Base(String s, boolean[][] dp) {
        for (int i = 0; i < s.length(); i++) {
            check4One(s, dp, i);
            check4Two(s, dp, i);
            check4Three(s, dp, i);
        }
    }

    private void check4One(String s, boolean[][] dp, int index) {
        if (s.charAt(index) == '*') {
            dp[index][index] = true;
        }
    }

    private void check4Two(String s, boolean[][] dp, int index) {
        //()  *)  (*  **
        if (s.length() <= index + 1) {
            return;
        }
        if ((s.charAt(index) == '(' && s.charAt(index + 1) == ')')
                || (s.charAt(index) == '*' && s.charAt(index + 1) == ')')
                || (s.charAt(index) == '(' && s.charAt(index + 1) == '*')
                || (s.charAt(index) == '*' && s.charAt(index + 1) == '*')) {
            dp[index][index + 1] = true;
            dp[index + 1][index] = true;
        }
    }

    private void check4Three(String s, boolean[][] dp, int index) {
        //(*)
        if (s.length() <= index + 2) {
            return;
        }
        if (s.charAt(index) == '(' && s.charAt(index + 1) == '*' && s.charAt(index + 2) == ')') {
            dp[index][index + 2] = true;
            dp[index + 2][index] = true;
        }
    }


    private boolean check4TwoChar(String s, int start, int end) {
        if (start < 0 || end >= s.length()) {
            return false;
        }
        return check4TwoChar(s.charAt(start), s.charAt(end));
    }

    private boolean check4TwoChar(char first, char second) {
        return (first == '(' || first == '*') && (second == ')' || second == '*');
    }

}
